백준 온라인 저지/출제된 문제/32454(r2 판)

상위 문서: 백준 온라인 저지/출제된 문제

Fibonacci Lucky Numbers
문제 번호		32454
기여자		목록 확인
레이팅		Platinum II
알고리즘		More 수학 정수론 분할 정복을 이용한 거듭제곱 오일러 피 함수 피사노 주기

1. 개요2. 풀이3. 정답 코드

3.1. C++

1. 개요 [편집]

To claim the jackpot, you need to compute the last $10$ digits of the $F_{7^{7^{7^n}}}$ , the $7^{7^{7^n}}$ -th Fibonacci number.

피보나치 수열의

7^{7^{7^n}}

번째 수의 마지막 10번째 자리까지 출력하면 되는 문제다.

2. 풀이 [편집]

당연히 쌩으로 구하기에는 매우 큰 수이다. 마지막 10번째 자리까지 출력하기 위해서는

10^{10}

로 나눈 나머지를 구하면 된다. 또한 피보나치 수에서 나누는 값이

2

보다 큰

m

에 대하여

10^{m}

라면 주기는

15 \times 10^{m-1}

인 피사노 주기를 이용할 수 있다. 여기서

m=10

이므로

{7^{7^{7^n}}} (\bmod \ 15 \times 10^{9})

번째 피보나치 수를

10^{10}

으로 나눈 나머지를 구하는 문제로 환원된다.

{7^{7^{7^n}}} (\bmod 15 \times 10^{9})

를 구하기 위해서는 오일러 공식을 활용하여 풀 수 있다.

m_0 = 15 \times 10^{9}, \quad m_1 = \varphi(m_0), \quad m_2 = \varphi(m_1)

라고 하자.

m_1

과

m_2

모두 7과 서로소이므로 다음과 같다.

e_1(n) = 7^{\,n \bmod m_2} \pmod{m_2}

e_2(n) = 7^{\,e_1(n) \bmod m_1} \pmod{m_1}

e_3(n) = 7^{\,e_2(n) \bmod m_0} \pmod{m_0}

7^{7^{7^n}} \bmod m_0 = e_3(n)

e_3(n)

을 구한 후,

e_3(n)

번째 피보나치 수를 구하면 된다. 이 값은

15 \times 10^{9}

보다 작으므로 피보나치 수를

\mathcal{O(\log n)}

방법으로 구하면 된다.

3. 정답 코드 [편집]

3.1. C++ [편집]

코드 보기/접기

#include <bits/stdc++.h>

#define fastio cin.tie(0), ios_base::sync_with_stdio(false)
using i64 = long long;
using u128 = unsigned __int128;
using namespace std;
i64 mod = (i64)1e10;

vector<vector<i64>> calc(const vector<vector<i64>>& m1, const vector<vector<i64>>& m2) {
    vector<vector<i64>> matrix(2, vector<i64>(2, 0));
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            u128 val = 0;
            for (int k = 0; k < 2; ++k) {
                val += (u128)m1[i][k] * (u128)m2[k][j];
            }
            matrix[i][j] = (i64)(val % (u128)mod);
        }
    }
    return matrix;
}

vector<vector<i64>> func(vector<vector<i64>> mat, i64 n) {
    vector<vector<i64>> res = {{1, 0}, {0, 1}};
    while (n > 0) {
        if (n & 1) res = calc(res, mat);
        mat = calc(mat, mat);
        n >>= 1;
    }
    return res;
}

i64 powmod(i64 a, i64 e, i64 m) {
    u128 A = (a % m + m) % m;
    u128 M = m;
    u128 r = 1;
    while (e > 0) {
        if (e & 1) r = (r * A) % M;
        A = (A * A) % M;
        e >>= 1;
    }
    return (i64)r;
}

int main() {
    fastio;
    int t;
    cin >> t;
    while (t--) {
        i64 n;
        cin >> n;

        vector<vector<i64>> matrix = {{1, 1}, {1, 0}};
        i64 e1 = powmod(7, n, 16LL*(i64)1e7);      // 160,000,000
        i64 e2 = powmod(7, e1, 4LL*(i64)1e8);      // 400,000,000
        i64 e3 = powmod(7, e2, 15LL*(i64)1e9);     // 15,000,000,000

        string rans;
        if (e3 <= 1) rans = string(9,'0') + char('0'+(int)e3);
        else {
            auto M = func(matrix, e3-1);
            i64 val = M[0][0] % mod;
            rans = to_string(val);
            if ((int)rans.size()<10) rans = string(10-rans.size(), '0')+rans;
        }
        cout << rans << '\n';
    }
    return 0;
}